﻿#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

class Solution
{
public:
    typedef long long ll;
    int minDifference(vector<int>& arr)
    {
        sort(arr.begin(), arr.end());
        ll ans = LLONG_MAX;
        ll n = arr.size();
        for (int i = 1; i < n; ++i)
        {
            ans = min(ans, (ll)arr[i] - arr[i - 1]);
        }

        return ans;
    }
};


//dfs

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    int Max = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
        Max = max(Max, arr[i]);
    }

    int ans = INT_MAX;
    vector<bool> check1(Max + 1, true);

    auto check = [](int n) -> bool
        {
            if (n <= 1)
            {
                return false;
            }
            for (int i = 2; i * i <= n; ++i)
            {
                if (n % i == 0)
                {
                    return false;
                }
            }
            return true;
        };

    function<void(int, int, int)> dfs = [&](int x, int sum, int count)
        {
            if (count == n)
            {
                ans = min(ans, sum);
                return;
            }

            for (int i = arr[x]; i > 0; --i)
            {
                if (arr[x] % i == 0 && check1[i] && check(i))
                {
                    check1[i] = false;

                    dfs(x + 1, sum + i, count + 1);

                    check1[i] = true;
                }
            }
        };

    dfs(0, 0, 0);

    if (ans == INT_MAX)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans << endl;
    }

    return 0;
}

//三题

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
    ll n;
    cin >> n;
    string s;
    cin >> s;

    vector<char> ans;
    for (char ch : s)
    {
        if (ans.empty() || ch >= ans.back())
        {
            ans.push_back(ch);
        }
        else
        {
            ll left = 0, right = ans.size() - 1;
            while (left < right)
            {
                ll mid = (left + right) / 2;
                if (ans[mid] > ch)
                {
                    right = mid;
                }
                else
                {
                    left = mid + 1;
                }
            }
            ans[left] = ch;
        }
    }

    cout << n - ans.size() << endl;
    return 0;
}


#include <iostream>
#include <string>
using namespace std;
const int N = 1e6 + 10;
int n;
string s;
char dp[N]; // dp[i] 表⽰：⻓度为 i 的所有的⼦序列中，最⼩的末尾是多少
int ret;
int main()
{
    cin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        char ch = s[i];
        // 找出 ch 应该放在哪个位置
        if (ret == 0 || ch >= dp[ret])
        {
            dp[++ret] = ch;
        }
        else
        {
            // ⼆分出 ch 应该放的位置
            int left = 1, right = ret;
            while (left < right)
            {
                int mid = (left + right) / 2;
                if (dp[mid] > ch) right = mid;
                else left = mid + 1;
            }
            dp[left] = ch;
        }
    }

    cout << n - ret << endl;

    return 0;
}